/*
 * @lc app=leetcode.cn id=572 lang=cpp
 *
 * [572] 另一棵树的子树
 *
 * https://leetcode-cn.com/problems/subtree-of-another-tree/description/
 *
 * algorithms
 * Easy (47.47%)
 * Likes:    688
 * Dislikes: 0
 * Total Accepted:    114.3K
 * Total Submissions: 240.7K
 * Testcase Example:  '[3,4,5,1,2]\n[4,1,2]'
 *
 * 
 * 
 * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true
 * ；否则，返回 false 。
 * 
 * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：root = [3,4,5,1,2], subRoot = [4,1,2]
 * 输出：true
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
 * 输出：false
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * root 树上的节点数量范围是 [1, 2000]
 * subRoot 树上的节点数量范围是 [1, 1000]
 * -10^4 
 * -10^4 
 * 
 * 
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {   
        if(root == NULL) return false;

        bool res1 = isSameTree(root, subRoot);
        bool res2 = isSubtree(root->left, subRoot);
        bool res3 = isSubtree(root->right, subRoot);
        return res1 || res2 || res3;
    }

    //递归法
    bool isSameTree(TreeNode* p, TreeNode* q) {

        //递归法
        if (p == NULL &&  q == NULL) return true;
        else if ((p != NULL && q == NULL) || (p ==NULL && q != NULL)) return false; 
        else if (p->val != q->val) return false;

        bool leftBool = isSameTree(p->left, q->left);
        bool rightBool = isSameTree(p->right, q->right);

        return leftBool && rightBool;


        // //迭代法
        // queue<TreeNode*> que;
        // TreeNode* pCur = p;
        // TreeNode* qCur = q;

        // que.push(pCur);
        // que.push(qCur);

        // while(!que.empty()){
        //     pCur = que.front();
        //     que.pop();
        //     qCur = que.front();
        //     que.pop();

        //     if(pCur == NULL && qCur == NULL) continue;
        //     else if ((pCur == NULL && qCur != NULL) || (pCur != NULL && qCur == NULL)) 
        //             return false;
        //     else if (pCur->val != qCur->val) return false;

        //     que.push(pCur->left);
        //     que.push(qCur->left);
        //     que.push(pCur->right);
        //     que.push(qCur->right);
        // }

        // return true;

    }

};
// @lc code=end

